#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

 struct TreeNode {
     int val;
    TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

    vector<TreeNode *> generateTreesHelper(int start, int end) {
	vector<TreeNode *> ans;
	if (start > end) {ans.push_back(NULL); return ans;}

	for (int i = start; i <= end; i++) {
//	    TreeNode *node = new TreeNode(i);
	    vector<TreeNode *> left = generateTreesHelper(start, i-1);
	    vector<TreeNode *> right = generateTreesHelper(i+1, end);
	    for (int k = 0; k < left.size(); k++) {
		for (int j = 0; j < right.size(); j++) {
		    //what a bug shoudl allocate here.
	            TreeNode *node = new TreeNode(i);
		    node->left = left[i];
		    node->right = right[j];
		    ans.push_back(node);
		}
	    }
	}        
	return ans;
    }

    vector<TreeNode *> generateTrees(int n) {
	return generateTreesHelper(1, n);
    }

int main(int argc, char **argv)
{
    cout << "-----------------Test 1--------------------" << endl;


    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
